#include <windows.h>
#include "resource.h"
#include <stdio.h>
#include <conio.h>
#include <time.h>

time_t rgr;

typedef struct aanod
{
	char cod[10]; // pt identificarea coord.
	char info[10];
	int level;
	aanod *left,*right,*Parent;
}aanod;

typedef struct rectt
{
	char cod[5];
	RECT coord;
}rectt;

int ran=0;
bool gasitt;
char *buff;
char *buffer;
int gasit=0;
aanod *Thead=NULL, *deleted=NULL,*last=NULL,*nodul=Thead;
HDC hdc;
PAINTSTRUCT Ps;
HWND hwndl=0,hwndl1=0,hwnd01=0;


rectt rect[31];

void Rebalance(aanod* x);

void initrect()
{
	strcpy(rect[0].cod,"*0000");
	rect[0].coord.left=27;
	rect[0].coord.top=455;
	rect[0].coord.right=rect[0].coord.left+53;
	rect[0].coord.bottom=rect[0].coord.top+40;

	strcpy(rect[1].cod,"*000");
	rect[1].coord.left=61;
	rect[1].coord.top=370;
	rect[1].coord.right=rect[1].coord.left+53;
	rect[1].coord.bottom=rect[1].coord.top+40;

	
	strcpy(rect[2].cod,"*0001");
	rect[2].coord.left=97;
	rect[2].coord.top=456;
	rect[2].coord.right=rect[2].coord.left+53;
	rect[2].coord.bottom=rect[2].coord.top+40;

	
	strcpy(rect[3].cod,"*00");
	rect[3].coord.left=132;
	rect[3].coord.top=261;
	rect[3].coord.right=rect[3].coord.left+53;
	rect[3].coord.bottom=rect[3].coord.top+40;

	
	strcpy(rect[4].cod,"*0010");
	rect[4].coord.left=167;
	rect[4].coord.top=455;
	rect[4].coord.right=rect[4].coord.left+53;
	rect[4].coord.bottom=rect[4].coord.top+40;

	
	strcpy(rect[5].cod,"*001");
	rect[5].coord.left=203;
	rect[5].coord.top=370;
	rect[5].coord.right=rect[5].coord.left+53;
	rect[5].coord.bottom=rect[5].coord.top+40;

	
	strcpy(rect[6].cod,"*0011");
	rect[6].coord.left=239;
	rect[6].coord.top=455;
	rect[6].coord.right=rect[6].coord.left+53;
	rect[6].coord.bottom=rect[6].coord.top+40;

	
	strcpy(rect[7].cod,"*0");
	rect[7].coord.left=280;
	rect[7].coord.top=136;
	rect[7].coord.right=rect[7].coord.left+53;
	rect[7].coord.bottom=rect[7].coord.top+40;

	
	strcpy(rect[8].cod,"*0100");
	rect[8].coord.left=313;
	rect[8].coord.top=455;
	rect[8].coord.right=rect[8].coord.left+53;
	rect[8].coord.bottom=rect[8].coord.top+40;

	
	strcpy(rect[9].cod,"*010");
	rect[9].coord.left=353;
	rect[9].coord.top=370;
	rect[9].coord.right=rect[9].coord.left+53;
	rect[9].coord.bottom=rect[9].coord.top+40;

	
	strcpy(rect[10].cod,"*0101");
	rect[10].coord.left=385;
	rect[10].coord.top=455;
	rect[10].coord.right=rect[10].coord.left+53;
	rect[10].coord.bottom=rect[10].coord.top+40;

	
	strcpy(rect[11].cod,"*01");
	rect[11].coord.left=425;
	rect[11].coord.top=260;
	rect[11].coord.right=rect[11].coord.left+53;
	rect[11].coord.bottom=rect[11].coord.top+40;

	
	strcpy(rect[12].cod,"*0110");
	rect[12].coord.left=458;
	rect[12].coord.top=455;
	rect[12].coord.right=rect[12].coord.left+53;
	rect[12].coord.bottom=rect[12].coord.top+40;

	
	strcpy(rect[13].cod,"*011");
	rect[13].coord.left=497;
	rect[13].coord.top=370;
	rect[13].coord.right=rect[13].coord.left+53;
	rect[13].coord.bottom=rect[13].coord.top+40;
	
	
	strcpy(rect[14].cod,"*0111");
	rect[14].coord.left=529;
	rect[14].coord.top=455;
	rect[14].coord.right=rect[14].coord.left+53;
	rect[14].coord.bottom=rect[14].coord.top+40;

	
	strcpy(rect[15].cod,"*");
	rect[15].coord.left=643;
	rect[15].coord.top=19;
	rect[15].coord.right=rect[15].coord.left+53;
	rect[15].coord.bottom=rect[15].coord.top+40;

	
	strcpy(rect[16].cod,"*1000");
	rect[16].coord.left=740;
	rect[16].coord.top=455;
	rect[16].coord.right=rect[16].coord.left+53;
	rect[16].coord.bottom=rect[16].coord.top+40;

	
	strcpy(rect[17].cod,"*100");
	rect[17].coord.left=780;
	rect[17].coord.top=370;
	rect[17].coord.right=rect[17].coord.left+53;
	rect[17].coord.bottom=rect[17].coord.top+40;

	
	strcpy(rect[18].cod,"*1001");
	rect[18].coord.left=816;
	rect[18].coord.top=455;
	rect[18].coord.right=rect[18].coord.left+53;
	rect[18].coord.bottom=rect[18].coord.top+40;

	
	strcpy(rect[19].cod,"*10");
	rect[19].coord.left=853;
	rect[19].coord.top=260;
	rect[19].coord.right=rect[19].coord.left+53;
	rect[19].coord.bottom=rect[19].coord.top+40;

	
	strcpy(rect[20].cod,"*1010");
	rect[20].coord.left=897;
	rect[20].coord.top=455;
	rect[20].coord.right=rect[20].coord.left+53;
	rect[20].coord.bottom=rect[20].coord.top+40;

	
	strcpy(rect[21].cod,"*101");
	rect[21].coord.left=933;
	rect[21].coord.top=370;
	rect[21].coord.right=rect[21].coord.left+53;
	rect[21].coord.bottom=rect[21].coord.top+40;

	
	strcpy(rect[22].cod,"*1011");
	rect[22].coord.left=972;
	rect[22].coord.top=455;
	rect[22].coord.right=rect[22].coord.left+53;
	rect[22].coord.bottom=rect[22].coord.top+40;

	
	strcpy(rect[23].cod,"*1");
	rect[23].coord.left=999;
	rect[23].coord.top=137;
	rect[23].coord.right=rect[23].coord.left+53;
	rect[23].coord.bottom=rect[23].coord.top+40;

	
	strcpy(rect[24].cod,"*1100");
	rect[24].coord.left=1041;
	rect[24].coord.top=455;
	rect[24].coord.right=rect[24].coord.left+53;
	rect[24].coord.bottom=rect[24].coord.top+40;

	
	strcpy(rect[25].cod,"*110");
	rect[25].coord.left=1076;
	rect[25].coord.top=370;
	rect[25].coord.right=rect[25].coord.left+53;
	rect[25].coord.bottom=rect[25].coord.top+40;

	
	strcpy(rect[26].cod,"*1101");
	rect[26].coord.left=1115;
	rect[26].coord.top=455;
	rect[26].coord.right=rect[26].coord.left+53;
	rect[26].coord.bottom=rect[26].coord.top+40;

	
	strcpy(rect[27].cod,"*11");
	rect[27].coord.left=1147;
	rect[27].coord.top=260;
	rect[27].coord.right=rect[27].coord.left+53;
	rect[27].coord.bottom=rect[27].coord.top+40;

	
	strcpy(rect[28].cod,"*1110");
	rect[28].coord.left=1185;
	rect[28].coord.top=455;
	rect[28].coord.right=rect[28].coord.left+53;
	rect[28].coord.bottom=rect[28].coord.top+40;

	
	strcpy(rect[29].cod,"*111");
	rect[29].coord.left=1220;
	rect[29].coord.top=370;
	rect[29].coord.right=rect[29].coord.left+53;
	rect[29].coord.bottom=rect[29].coord.top+40;

	
	strcpy(rect[30].cod,"*1111");
	rect[30].coord.left=1257;
	rect[30].coord.top=455;
	rect[30].coord.right=rect[30].coord.left+53;
	rect[30].coord.bottom=rect[30].coord.top+40;
}

void encodearb(aanod *p,aanod *dad,char c[])
{
	if (p==NULL) return;
	if (p==Thead->left) 
	{
		strcpy(p->cod,"*");
	}
	else if (p!=dad)
	{
		strcpy(p->cod,dad->cod);
		strcat(p->cod,c);
	}
	encodearb(p->left,p,"0");
	encodearb(p->right,p,"1");
}

int compara(char a[5],char b[5])
{
	if (strlen(a)<strlen(b)) return -1;
	if (strlen(a)>strlen(b)) return 1;
	if (strcmp(a,b)<0) return -1;
	if (strcmp(a,b)==0) return 0;
	if (strcmp(a,b)>0) return 1;

}

void insertarb(aanod *p,aanod *deinserat)
{

	if (Thead==NULL) 
	{
		strcpy(deinserat->cod,"*");
		Thead=deinserat;
		return;
	}
	
	if ((compara(deinserat->info,p->info)>0)&&(p->right==NULL)) {p->right=deinserat; return;}
	if ((compara(deinserat->info,p->info)<0)&&(p->left==NULL)) {p->left=deinserat; return;}

	if ((compara(deinserat->info,p->info)<0)&&(p->left!=NULL)) insertarb(p->left,deinserat);
	if ((compara(deinserat->info,p->info)>0)&&(p->right!=NULL)) insertarb(p->right,deinserat);
}

int cautacodu(char s[5])
{
	for (int i=0;i<31;i++)
		if (!strcmp(s,rect[i].cod)) {  return i; }
		return -1;
}

void linie(RECT dad,  RECT p)
{
        MoveToEx(hdc  ,dad.right-26  ,dad.bottom,NULL);  
        LineTo(hdc  ,p.left+26  ,p.top-3);
}

void scrielevel(RECT r,aanod *p,aanod *ss)
{
	RECT r1;
	char s[10];
	r1.left=r.left;
	r1.top=r.top+(r.bottom-r.top)/2;
	r1.right=r.right;
	r1.bottom=r.bottom;
	itoa(p->level,s,10);
	if (compara(p->info,ss->info))
		SetTextColor(hdc,RGB(255,81,94));
	DrawText(hdc,s,strlen(s),&r1,DT_CENTER);
	if (compara(ss->info,p->info))
		SetTextColor(hdc,RGB(0,0,0));
}

void afisarearb(aanod *p,aanod *s)
{
	if (p==NULL) return;

	if (( p->left && p!=Thead)&&(cautacodu(p->cod)!=-1)&&(cautacodu(p->cod)%2!=0)) linie(rect[cautacodu(p->cod)].coord,rect[cautacodu(p->left->cod)].coord);
	afisarearb(p->left,s);
	
	int x=cautacodu(p->cod); 

	if (x!=-1)
	{
	Rectangle(hdc,rect[x].coord.left,rect[x].coord.top-2,rect[x].coord.right,rect[x].coord.bottom);
	if (gasitt && compara(s->info,p->info)==0) 
	{
		SetTextColor(hdc,RGB(0,255,0));
	}
	DrawText(hdc,p->info,strlen(p->info),&rect[x].coord,DT_CENTER);
	scrielevel(rect[x].coord,p,s);	
	if (gasitt && compara(s->info,p->info)==0)
	{
		SetTextColor(hdc,RGB(0,0,0));
		
	}
	if (( p->right && p!=Thead)&&(cautacodu(p->cod)!=-1)&&(cautacodu(p->cod)%2!=0)) linie(rect[cautacodu(p->cod)].coord,rect[cautacodu(p->right->cod)].coord);	
	}
	afisarearb(p->right,s);
}

// primul parametru este nodul caruia vream sa ii gasim parintele
aanod *fathertree(aanod *celcautat,aanod *p) 
{	
	if (p==NULL) return  NULL;
	if ((p->left!=NULL)&&(p->left==celcautat)) return p;
	if ((p->right!=NULL)&&(p->right==celcautat)) return p;
	if (p==celcautat) return p; // tatal lui head este tot head
	if (compara(celcautat->info,p->info)<0) fathertree(celcautat,p->left);
	else if (compara(celcautat->info,p->info)>0) fathertree(celcautat,p->right);
}


//---------------------------------------------------------------------------------


void Skew(aanod *x)
{
	//-------------------------
		
			sprintf(buff,"__facem skew deoarece nodul stang %s are acelasi level ca si %s care este nodul curent__",x->left->info,x->info);
			strcat(buffer,buff);
			
		//-------------------------


   aanod *y;
   y = x->left;
   // Move X from its parent
   if ( x->Parent->left == x )
     x->Parent->left = y;
   else
     x->Parent->right = y;
     
   // Set parents
   y->Parent = x->Parent;
   x->Parent = y;

   x->left = y->right;

   // X's left's parent becomes X
   if ( x->left != NULL )
    x->left->Parent = x;
    
   // Hang X on Y's right
   y->right = x;
   
   // Set level
   x->level = (x->left ? x->left->level+1 : 1);

}


bool Split(aanod* x)
{
	

   aanod *y;
   y = x->right;
   //-------------------------------
		{
			  sprintf(buff,"__[pozitia curenta:%s]",x->info);
			strcat(buffer,buff);
		 }
	//-------------

   // Perform left rotation if Y has a child Right and its level is == X's level
   if ( y && y->right && (y->right->level == x->level))
   {
	    //-------------------------
		
	   sprintf(buff,"__facem SPLIT deoarece nodurile din dreapta care au acelasi level sunt prea multe__",x->info,x->info);
				strcat(buffer,buff);
			
		//-------------------------

     if ( x->Parent->left == x )
      x->Parent->left = y;
     else
      x->Parent->right = y;
      
     y->Parent = x->Parent;
     x->Parent = y;
     
     x->right = y->left;
     
     if ( x->right != NULL )
      x->right->Parent = x;
      
     y->left = x;
     
     y->level = x->level+1;
     
     return true;
   }
   
   return false;
}


void Rebalance(aanod* x)
{
  x->level = 1;
  x->left = x->right = NULL;
  
  // Climmb up the tree and balance
  for ( x = x->Parent; x != Thead; x = x->Parent )
  {
	  //----------------------
	
	  //--------------------------------
     if ( x->level != (x->left ? x->left->level + 1 : 1 ))
     {
		  {
			sprintf(buff,"__[pozitia curenta:%s]",x->info);
			strcat(buffer,buff);
	      }
        Skew(x); 
        
        if ( (x->right == NULL) || (x->level != x->right->level))
         x = x->Parent;
     }
     
     if ( (x->Parent != Thead) && (Split(x->Parent) == false) )
	 {  
		 break;
	 }
  }
}

// primul parametru headu si al doilea nodul de inserat
void Insert(aanod* x, aanod* insert)
{
	if ( Thead != NULL && Thead->left ==NULL)
	{
		//-------------------------
		strcat(buffer,"__Am plantat head-ul deoarece nu exista__");
		//-------------------------
	}

     if ( Thead == NULL )
     {  
		 insert->level=1;	
	   insert->left = insert->right = NULL;
       Thead = insert;
       return ;
     }

     // left?
	//-------------------------




	//-------------------------
     if (compara(insert->info,x->info)<0)
     {
		 //-------------------------
		 if (x!=Thead)
			{
			sprintf(buff,"__%s<%s__",insert->info,x->info);
			strcat(buffer,buff);
			}
		 //-------------------------

        if ( x->left ) // mergem la stanga
		{  
			
			//-------------------------
			if (x!=Thead)
			{
			sprintf(buff,"__ne deplasam cu un nod spre stanga__",insert->info,x->info);
			strcat(buffer,buff);
			}
			//-------------------------
			
			
			Insert( x->left, insert );
			return ;
		}
		 
        // daca nu adaugam nodul in stanga

		//-------------------------
		if (x!=Thead)
			{
				sprintf(buff,"__deoarece la stanga lui %s este NULL inseram nodul la stanga lui %s__",x->info,x->info);
				strcat(buffer,buff);
			}
		//-------------------------
		x->left = insert;
		insert->Parent=x;
        Rebalance(insert); 

        return ;
     }

     //right?
     if (compara(insert->info,x->info)>0)
     {
		 //-------------------------
		 if (x!=Thead)
			{
			sprintf(buff,"__%s>%s__",insert->info,x->info);
			strcat(buffer,buff);
			}
		 //-------------------------

		 if ( x->right ) // mergem spre dreapta
		 { 

			 //-------------------------
			if (x!=Thead)
			{
				sprintf(buff,"__ne deplasam cu un nod spre dreapta__",insert->info,x->info);
				strcat(buffer,buff);
			}
			//-------------------------

			 Insert( x->right, insert ); 
			 return; 
		 }

        // daca nu inseram in dreapta
	    //-------------------------
		if (x!=Thead)
			{
				sprintf(buff,"__deoarece la dreapta lui %s este NULL inseram nodul la dreapta lui %s__",x->info,x->info);
				strcat(buffer,buff);
			}
		//-------------------------

        x->right = insert;
        insert->Parent = x;
        Rebalance(insert);

        return ;
     }

     delete insert;
	 return ;
}


aanod *CautacelMaiStang(aanod *p)
{
	if (p->left==NULL) return p;
	CautacelMaiStang(p->left);
}

void searchnod(aanod *p,aanod *decautat,int *h)
{
	if (p==NULL) { (*h)--; return; }
	if (compara(decautat->info,p->info)==0) {gasitt=true; return; }
	if (compara(decautat->info,p->info)<0)
	{
		(*h)++;
		searchnod(p->left,decautat,h);
	}
	if (compara(decautat->info,p->info)>0)
	{
		(*h)++;
		searchnod(p->right,decautat,h);
	}
	(*h)--;
}

void random()
{
	int x,y,i;
	time(&rgr);
	if (ran) return;
	ran++;	
	x=rand()%15+1;
	srand ((unsigned int )rgr);
	for (i=0;i<x;i++)
	{
		gasit=1;
		y=rand()%1000;
		char s[5];
		sprintf(s,"%d",y);
		aanod *p=(aanod *)malloc(sizeof(aanod));
		p->left=p->right=NULL;
		strcpy(p->info,s);
			// in functia insert se foloseste bufferu si de aceea am alocat memorie pt el
			free(buff);	
			free(buffer);		
			buffer=(char *)malloc(10000*sizeof(char));
			buff=(char *)malloc(1000*sizeof(char));
			sprintf(buffer,"[%s] ",s);									
			strcpy(buffer,"ss");

			UpdateWindow(hwndl1);
			Insert(Thead, p);
			encodearb(Thead,Thead,"-");
			
			SendMessage(hwnd01,WM_PAINT,(WPARAM )hdc,0);
	}
	
}

void clearmemory(aanod *p,int k)
{
	if (p==NULL) return;
	if (p->left==NULL && p->right==NULL) 
	{
		if (k==0)	p->Parent->left=NULL;
		if (k==1)	p->Parent->right=NULL;
		free(p);
		return;
	}
	clearmemory(p->left,0);
	clearmemory(p->right,1);
}

// returneaza daca stringu poate reprezenta un integer
int integer(char *s)
{
	int i,x=strlen(s);
	for (i=0;i<x;i++)
		if (!isdigit(s[i])) return 0; // daca intalneste un caracter infara de digituri 
	if (x==1 && s[0]=='0') return 1; // cazul lui 0
	for (i=0;i<x;i++) 
	{
		if (s[i]!='0') break;    // daca nu incepe cu 0 e bine 
		if (s[i]=='0') return 0; // daca incepe integeru cu 0 
	}
	return 1;
}